package com.leetcode.algorithm.y22.m09.w1;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * 135. 分发糖果
 * 
 * https://leetcode.cn/problems/candy/
 * 
 * @author jie.deng
 *
 */
class Question0135Solution01 {

	public int candy(int[] ratings) {
		// 局部最优:(两次贪心)
		// 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
		// 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
		int len = ratings.length;
		int[] cntArr = new int[len];
		Arrays.fill(cntArr, 1);
		for (int i = 1; i < ratings.length; i++) {
			if (ratings[i] > ratings[i - 1]) {
				cntArr[i] = cntArr[i - 1] + 1;
			}
		}
		for (int i = len - 1; i >= 1; i--) {
			if (ratings[i - 1] > ratings[i] && cntArr[i - 1] <= cntArr[i]) {
				cntArr[i - 1] = cntArr[i] + 1;
			}
		}
		return IntStream.of(cntArr).sum();
	}

}